#include <bits/stdc++.h>

# define INF 0x7fffffff;  // 无穷大
typedef long long ll;

using namespace std;

class Solution {
public:
    int minimumAddedInteger(vector<int>& a, vector<int>& b) {
        int ans = 0;
        ranges::sort(a, greater());
        ranges::sort(b, greater());
        for (int s = 0; s <= 2; s++) {
            int p1 = s, p2 = 0, diff_cnt = 0;
            while (p1 < a.size() - 1 && p2 < b.size() - 1) {
                int next = p1 + 1;
                while (next < a.size() && a[next] - a[p1] != b[p2 + 1] - b[p2]) {diff_cnt++;next++;}
                p1 = next;
                p2++;
            }
            if (diff_cnt <= (2 - s) ) {
                ans = b[0] - a[s];
                break;
            }
        }
        return ans;
    }
};

int main(int argc, const char** argv) {
    Solution s;
    vector<int> a = {0, 7, 10, 8, 9, 9};
    vector<int> b = {8, 9, 10, 10};
    a = {4, 20, 16, 12, 8};
    b = {14, 18, 10};
    auto res = s.minimumAddedInteger(a, b);
    std::cout << res << std::endl;

    a = {3, 5, 5, 3};
    b = {7, 7};
    res = s.minimumAddedInteger(a, b);
    std::cout << res << std::endl;

    a = {9, 4, 3, 9, 4};
    b = {7, 8, 8};
    res = s.minimumAddedInteger(a, b);
    std::cout << res << std::endl;

    a = {0, 7, 10, 8, 9, 9};
    b = {8, 9, 10, 10};
    res = s.minimumAddedInteger(a, b);
    std::cout << res << std::endl;
    return 0;
}
